<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>算法图解：除自身以外数组的乘积</title>
    <link rel="stylesheet" href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css">
    <link rel="stylesheet" href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <script src="https://cdn.jsdelivr.net/npm/mermaid@latest/dist/mermaid.min.js"></script>
    <style>
        body {
            font-family: 'Noto Sans SC', Tahoma, Arial, Roboto, "Droid Sans", "Helvetica Neue", "Droid Sans Fallback", "Heiti SC", "Hiragino Sans GB", Simsun, sans-serif;
            background-color: #f8fafc;
            color: #1e293b;
        }
        .hero-gradient {
            background: linear-gradient(135deg, #6366f1 0%, #8b5cf6 100%);
        }
        .code-block {
            background-color: #1e293b;
            border-radius: 0.5rem;
        }
        .concept-card {
            transition: all 0.3s ease;
            box-shadow: 0 4px 6px -1px rgba(0, 0, 0, 0.1), 0 2px 4px -1px rgba(0, 0, 0, 0.06);
        }
        .concept-card:hover {
            transform: translateY(-4px);
            box-shadow: 0 10px 15px -3px rgba(0, 0, 0, 0.1), 0 4px 6px -2px rgba(0, 0, 0, 0.05);
        }
        .diagram-container {
            background-color: white;
            border-radius: 1rem;
            box-shadow: 0 4px 6px -1px rgba(0, 0, 0, 0.1), 0 2px 4px -1px rgba(0, 0, 0, 0.06);
        }
    </style>
</head>
<body>
    <!-- Hero Section -->
    <section class="hero-gradient text-white py-20">
        <div class="container mx-auto px-6">
            <div class="max-w-4xl mx-auto text-center">
                <h1 class="text-4xl md:text-5xl font-bold mb-6 font-serif">除自身以外数组的乘积</h1>
                <p class="text-xl md:text-2xl mb-8 opacity-90">探索高效解决数组乘积问题的巧妙算法</p>
                <div class="w-24 h-1 bg-white opacity-50 mx-auto mb-8"></div>
                <p class="text-lg md:text-xl mb-10 leading-relaxed max-w-2xl mx-auto">通过左右乘积法在O(n)时间内解决问题，不使用除法，仅需常数额外空间</p>
                <div class="flex flex-wrap justify-center gap-4">
                    <span class="px-4 py-2 bg-white bg-opacity-20 rounded-full text-sm font-medium">#数组处理</span>
                    <span class="px-4 py-2 bg-white bg-opacity-20 rounded-full text-sm font-medium">#前缀积</span>
                    <span class="px-4 py-2 bg-white bg-opacity-20 rounded-full text-sm font-medium">#后缀积</span>
                    <span class="px-4 py-2 bg-white bg-opacity-20 rounded-full text-sm font-medium">#空间优化</span>
                </div>
            </div>
        </div>
    </section>

    <!-- Problem Description -->
    <section class="py-16 bg-white">
        <div class="container mx-auto px-6 max-w-5xl">
            <div class="flex items-center mb-8">
                <i class="fas fa-question-circle text-3xl mr-4 text-indigo-500"></i>
                <h2 class="text-3xl font-bold font-serif">问题描述</h2>
            </div>
            <div class="bg-slate-50 p-6 rounded-xl border border-slate-200">
                <p class="text-lg leading-relaxed mb-4">给定一个包含 <span class="font-bold text-indigo-600">n</span> 个整数的数组 <span class="font-mono bg-slate-200 px-2 py-1 rounded">nums</span>，返回一个新数组 <span class="font-mono bg-slate-200 px-2 py-1 rounded">output</span>，其中 <span class="font-mono bg-slate-200 px-2 py-1 rounded">output[i]</span> 等于除 <span class="font-mono bg-slate-200 px-2 py-1 rounded">nums[i]</span> 之外所有元素的乘积。</p>
                <p class="text-lg leading-relaxed mb-4"><span class="font-bold text-indigo-600">要求：</span></p>
                <ul class="list-disc pl-6 space-y-2 mb-4">
                    <li>不能使用除法</li>
                    <li>时间复杂度必须为 O(n)</li>
                    <li>空间复杂度为 O(1)（不计输出数组）</li>
                </ul>
                <p class="text-lg leading-relaxed"><span class="font-bold text-indigo-600">示例：</span> 输入 <span class="font-mono bg-slate-200 px-2 py-1 rounded">[1, 2, 3, 4]</span>，输出 <span class="font-mono bg-slate-200 px-2 py-1 rounded">[24, 12, 8, 6]</span></p>
            </div>
        </div>
    </section>

    <!-- Algorithm Explanation -->
    <section class="py-16 bg-slate-50">
        <div class="container mx-auto px-6 max-w-5xl">
            <div class="flex items-center mb-8">
                <i class="fas fa-lightbulb text-3xl mr-4 text-indigo-500"></i>
                <h2 class="text-3xl font-bold font-serif">算法思路</h2>
            </div>
            
            <div class="grid md:grid-cols-2 gap-8 mb-12">
                <div class="concept-card p-6 bg-white rounded-xl">
                    <div class="flex items-center mb-4">
                        <div class="w-10 h-10 rounded-full bg-indigo-100 text-indigo-600 flex items-center justify-center mr-4">
                            <i class="fas fa-arrow-left"></i>
                        </div>
                        <h3 class="text-xl font-bold">左侧乘积</h3>
                    </div>
                    <p class="text-slate-600">从左到右遍历数组，计算每个元素左侧所有元素的乘积。初始时左侧乘积为1（因为第一个元素左侧没有元素）。</p>
                </div>
                
                <div class="concept-card p-6 bg-white rounded-xl">
                    <div class="flex items-center mb-4">
                        <div class="w-10 h-10 rounded-full bg-purple-100 text-purple-600 flex items-center justify-center mr-4">
                            <i class="fas fa-arrow-right"></i>
                        </div>
                        <h3 class="text-xl font-bold">右侧乘积</h3>
                    </div>
                    <p class="text-slate-600">从右到左遍历数组，计算每个元素右侧所有元素的乘积。初始时右侧乘积为1（因为最后一个元素右侧没有元素）。</p>
                </div>
            </div>
            
            <div class="mb-8">
                <h3 class="text-2xl font-bold mb-6 font-serif">可视化过程</h3>
                <div class="diagram-container p-6">
                    <div class="mermaid">
                        graph LR
                            A[输入数组: 1, 2, 3, 4] --> B[左侧乘积: 1, 1, 2, 6]
                            A --> C[右侧乘积: 24, 12, 4, 1]
                            B --> D[结果数组: 1*24=24, 1*12=12, 2*4=8, 6*1=6]
                            C --> D
                    </div>
                </div>
            </div>
            
            <div class="concept-card p-6 bg-white rounded-xl">
                <div class="flex items-center mb-4">
                    <div class="w-10 h-10 rounded-full bg-green-100 text-green-600 flex items-center justify-center mr-4">
                        <i class="fas fa-cog"></i>
                    </div>
                    <h3 class="text-xl font-bold">空间优化</h3>
                </div>
                <p class="text-slate-600 mb-4">我们可以直接使用输出数组 <span class="font-mono bg-slate-200 px-2 py-1 rounded">result</span> 来存储左侧乘积，然后在计算右侧乘积时直接乘到 <span class="font-mono bg-slate-200 px-2 py-1 rounded">result</span> 中，从而将空间复杂度优化到 O(1)（不计输出数组）。</p>
                <p class="text-slate-600">这种方法巧妙地利用了输出数组的存储空间，避免了使用额外的数组来存储左侧和右侧乘积。</p>
            </div>
        </div>
    </section>

    <!-- Code Implementation -->
    <section class="py-16 bg-white">
        <div class="container mx-auto px-6 max-w-5xl">
            <div class="flex items-center mb-8">
                <i class="fas fa-code text-3xl mr-4 text-indigo-500"></i>
                <h2 class="text-3xl font-bold font-serif">代码实现</h2>
            </div>
            
            <div class="code-block p-4 rounded-lg mb-8">
                <div class="flex items-center text-slate-400 mb-4">
                    <div class="w-3 h-3 rounded-full bg-red-500 mr-2"></div>
                    <div class="w-3 h-3 rounded-full bg-yellow-500 mr-2"></div>
                    <div class="w-3 h-3 rounded-full bg-green-500 mr-2"></div>
                    <span class="ml-2 text-sm">Python</span>
                </div>
                <pre class="text-slate-100 overflow-x-auto"><code>def productExceptSelf(nums):
    n = len(nums)
    result = [1] * n
    
    # 计算左侧乘积
    left = 1
    for i in range(n):
        result[i] *= left
        left *= nums[i]
    
    # 计算右侧乘积并合并
    right = 1
    for i in range(n-1, -1, -1):
        result[i] *= right
        right *= nums[i]
    
    return result</code></pre>
            </div>
            
            <div class="grid md:grid-cols-2 gap-8">
                <div class="bg-slate-50 p-6 rounded-xl">
                    <h3 class="text-xl font-bold mb-4 flex items-center">
                        <i class="fas fa-clock mr-3 text-indigo-500"></i>
                        时间复杂度分析
                    </h3>
                    <p class="text-slate-600">该算法进行了两次遍历数组的操作：</p>
                    <ul class="list-disc pl-6 mt-2 space-y-2">
                        <li>第一次从左到右遍历计算左侧乘积</li>
                        <li>第二次从右到左遍历计算右侧乘积</li>
                    </ul>
                    <p class="mt-4 font-medium">总时间复杂度为 O(n) + O(n) = <span class="text-indigo-600">O(n)</span></p>
                </div>
                
                <div class="bg-slate-50 p-6 rounded-xl">
                    <h3 class="text-xl font-bold mb-4 flex items-center">
                        <i class="fas fa-memory mr-3 text-indigo-500"></i>
                        空间复杂度分析
                    </h3>
                    <p class="text-slate-600">该算法仅使用了有限的几个变量：</p>
                    <ul class="list-disc pl-6 mt-2 space-y-2">
                        <li>输出数组 <span class="font-mono bg-slate-200 px-2 py-1 rounded">result</span>（不计入空间复杂度）</li>
                        <li>变量 <span class="font-mono bg-slate-200 px-2 py-1 rounded">left</span> 和 <span class="font-mono bg-slate-200 px-2 py-1 rounded">right</span></li>
                    </ul>
                    <p class="mt-4 font-medium">总空间复杂度为 <span class="text-indigo-600">O(1)</span>（不计输出数组）</p>
                </div>
            </div>
        </div>
    </section>

    <!-- Application Example -->
    <section class="py-16 bg-indigo-50">
        <div class="container mx-auto px-6 max-w-5xl">
            <div class="flex items-center mb-8">
                <i class="fas fa-rocket text-3xl mr-4 text-indigo-500"></i>
                <h2 class="text-3xl font-bold font-serif">实际应用</h2>
            </div>
            
            <div class="bg-white p-6 rounded-xl shadow-sm">
                <p class="text-lg leading-relaxed mb-4">"除自身以外数组的乘积"算法在实际中有多种应用场景：</p>
                <ul class="list-disc pl-6 space-y-3">
                    <li><span class="font-bold">信号处理：</span> 计算滑动窗口内其他元素的乘积，用于平滑或滤波处理</li>
                    <li><span class="font-bold">图像处理：</span> 像素值计算时排除当前像素的影响</li>
                    <li><span class="font-bold">统计计算：</span> 计算数据集中每个元素与其他元素的关系</li>
                    <li><span class="font-bold">推荐系统：</span> 计算用户评分时排除自身评分的影响</li>
                </ul>
            </div>
        </div>
    </section>

    <script>
        mermaid.initialize({
            startOnLoad: true,
            theme: 'default',
            flowchart: {
                useMaxWidth: true,
                htmlLabels: true,
                curve: 'basis'
            }
        });
    </script>
</body>
</html>